package hot;

/**
 * @author way
 * @create 2025-03-20 10:57
 */
public class _31_nextPermutation {
    public void nextPermutation(int[] nums) {
        if (nums.length <= 1) return;

        int i = nums.length - 2;
        int j = nums.length - 1;
        int k = nums.length - 1;

        // 寻找第一个升序对 nums[i] < nums[j]
        while (i >= 0 && nums[i] >= nums[j]) {
            i--;
            j--;
        }

        if (i >= 0) { // 如果不是完全逆序的最后一个排列
            // 寻找第一个大于 nums[i] 的 nums[k]
            while (nums[i] >= nums[k]) {
                k--;
            }
            // 交换 nums[i] 和 nums[k]
            swap(nums, i, k);
        }

        // 反转 j 之后的部分
        reverse(nums, j, nums.length - 1);
    }

    // 交换数组元素
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    // 反转子数组
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}
